(defun permute (list)
  (cond
    ((endp list) list)                  ; no permutations of ()
    ((endp (cdr list)) (list list))     ; one permutation of (x)
    (t (loop :for subpermutation :in (permute (cdr list)) :nconc
          (loop :for i :from 0 :to (length subpermutation)
             :collecting (append (subseq subpermutation 0 i)
                                 (cons (car list) (subseq subpermutation i)))))))) 

(defun permutations (items &aux result)
   (if items
       (dolist (item items result)
        (dolist (permutation (permutations (remove item items)))
          (push (cons item permutation) result)))
       '(nil))) 